package leetcode_600;



/**
 *@author 周杨
 *OutOfBoundaryPaths_576 记录有多少种方式能让皮球出界
 *describe:用动态规划
 *2018年9月17日 上午9:50:39
 */
public class OutOfBoundaryPaths_576 {
	int m;
	int n;
	int dp[][][];
	
	static int[][] ops = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    public int findPaths1(int m, int n, int N, int i, int j) {
        long[][][] dp = new long[N][m][n];
        return (int) bt(dp, m, n, N, i, j);
    }
    private long bt(long[][][] dp, int m, int n, int N, int i, int j) {
        if (0 > i || 0 > j || m == i || n == j) return 1;
        if (0 == N || (Math.min(i, j) > N && m - i > N && n - j > N)) return 0;
        if (0 != dp[N - 1][i][j]) {
            return -1 == dp[N - 1][i][j] ? 0 : dp[N - 1][i][j];
        }
        long total = 0;
        for (int[] op : ops) {
            total += bt(dp, m, n, N - 1, i + op[0], j + op[1]) % 1000000007;
        }
        total %= 1000000007;
        dp[N - 1][i][j] = 0 == total ? -1 : total;
        return total;
    }
	/**
	 * describe:正确解 没有取模
	 * 2018年9月17日 上午9:51:29
	 */
	public int findPaths(int m, int n, int N, int i, int j) {
		this.m=m;
		this.n=n;
        this.dp=new int[m][n][N+1];
        int res=0;
        for(int k=1;k<=N;++k) {
        	res+= help(i,j,k);
        }
        return res;
    }
	
	public int help(int i,int j,int N) {
		if(i<0||i==m||j<0||j==n)
			return 0;
		if(dp[i][j][N]==-1)//走不到的标记位
			return 0;
		if(dp[i][j][N]!=0)
			return dp[i][j][N];
		if(N==1) {
			int res=0;
			if(i==0)
				++res;
			if(i==m-1)
				++res;
			if(j==0)
				++res;
			if(j==n-1)
				++res;
			dp[i][j][N]=res==0?-1:res;
			return res;
		}
		dp[i][j][N]=help(i-1,j,N-1)+help(i+1,j,N-1)+
				help(i,j-1,N-1)+help(i,j+1,N-1);
		return dp[i][j][N];
		
	}
}
